#if !defined(STLHELPER_H)
#define STLHELPER_H
// stlhelper.h : helper functions and macros
//
/////////////////////////////////////////////////////////////////////////////


#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
#include <deque>
#include <string>
#include <cassert>
#include <stdexcept>

#ifdef _MY_STL_MACROS
#define beg_to_end(container) (container).begin(),(container).end()
#define for_iter(container, iter_type, iter) \
   for(iter_type iter = (container).begin(); \
      iter != (container).end(); ++iter)
#endif

/*
		str_search_and_replace
		count_removed_duplicates
		remove_duplicates
		includes
		includes
		copy_if
		for_each_if
		for_each_stride
		erase_if_found
		min_max_element
		set_mark_union
		set_mark_diff
		mark_consecutive_duplicates
		op_ignore
*/

namespace stlhelper
{
template<typename T>
struct t_map_lookup
{
	const T& value;
	t_map_lookup(const T& value_):value(value_){}

	template<typename CONT >
	const typename CONT::mapped_type& in(const CONT& data) const                                      
	{                                                                              
		if (data.count(value) == 0)
			throw std::runtime_error("Value not found.\n");
		return data.find(value)->second;
	}                                                                              
};

template<typename T>
t_map_lookup<T> lookup(const T& t)
{
	return t;
}
}

template <typename T, typename function>
struct op_less_indices : public std::binary_function<unsigned,unsigned,bool>
{
	const std::vector<T>& data;
	function f;
	op_less_indices(std::vector<T>& data_, function f_) :data(data_), f(f_){}
	bool operator()(unsigned x, unsigned y) const { return f(data[x], data[y]); }
};


template<typename T, typename function>
void sort_indices(std::vector<T>& data, std::vector<unsigned>& indices, function f = function())
{
	indices.clear();
	for (unsigned i = 0; i < data.size(); ++i)
		indices.push_back(i);
	op_less_indices<T, function> less_after_indexing(data, f);
	sort(indices.begin(), indices.end(), less_after_indexing);
}

template<typename T>
void sort_indices(std::vector<T>& data, std::vector<unsigned>& indices)
{
	indices.clear();
	for (unsigned i = 0; i < data.size(); ++i)
		indices.push_back(i);
	op_less_indices<T, std::less<T> > less_after_indexing(data, std::less<T>());
	sort(indices.begin(), indices.end(), less_after_indexing);
}




template <typename ITER, typename function>
struct op_less_offset : public std::binary_function<unsigned,unsigned,bool>
{
	ITER iter;
	function f;
	op_less_offset(ITER iter_, function f_) :iter(iter_), f(f_){}
	bool operator()(unsigned x, unsigned y) const { return f(*(iter + x), *(iter + y)); }
};


template<typename ITER, typename function>
void sort_indices(ITER beg, ITER end, std::vector<unsigned>& indices, function f = function())
{
	indices.clear();
	unsigned size = end - beg;
	for (unsigned i = 0; i < size; ++i)
		indices.push_back(i);
	op_less_offset<ITER, function> less_after_offset(beg, f);
	sort(indices.begin(), indices.end(), less_after_offset);
}

template<typename ITER>
void sort_indices(ITER beg, ITER end, std::vector<unsigned>& indices)
{
	indices.clear();
	unsigned size = end - beg;
	for (unsigned i = 0; i < size; ++i)
		indices.push_back(i);
    typedef typename std::iterator_traits<ITER>::value_type value_type;
	op_less_offset<ITER, std::less<value_type> > less_after_offset(beg, std::less<value_type>());
	sort(indices.begin(), indices.end(), less_after_offset);
}







// sorts in place
template<typename CONT >
void order_by_sorted_indices(CONT& data, std::vector<unsigned> indices)
{
	assert(data.size() >= indices.size());

	std::vector<unsigned> curr_order(indices.size());
	for (unsigned i = 0; i < indices.size(); ++i)
		curr_order[indices[i]] = i;

	for (unsigned j = 0; j < indices.size(); ++j)
	{
		using std::swap;
		assert(indices[j] < data.size());
		if (curr_order[j] == j)
			continue;
		unsigned index  = indices[j];
		std::swap(indices[curr_order[j]], indices[j]);
		std::swap(curr_order[j], curr_order[index]);
		swap(data[j], data[index]);

	}
}


template<typename randIter>
void order_by_sorted_indices(randIter first, randIter last, std::vector<unsigned> indices)
{
	assert(std::distance(first, last) >= (int)indices.size());

	std::vector<unsigned> curr_order(indices.size());
	for (unsigned i = 0; i < indices.size(); ++i)
		curr_order[indices[i]] = i;

	for (unsigned j = 0; j < indices.size(); ++j)
	{
		using std::swap;
		assert(int(indices[j]) < std::distance(first, last));
		if (curr_order[j] == j)
			continue;
		unsigned index  = indices[j];
		std::swap(indices[curr_order[j]], indices[j]);
		std::swap(curr_order[j], curr_order[index]);
		swap(*(first + j), *(first + index));
	}
}










template <typename InputIter, typename function>
struct less_indirect : public std::binary_function<InputIter,InputIter,bool>
{
	function f;
	less_indirect(function f_): f(f_){}
	bool operator()(InputIter x, InputIter y) const { return f(*x,*y); }
};

/*
template<typename function, typename randIter>
void sort_with_swaps(randIter first, randIter last, function f)
{
    typedef typename std::iterator_traits<randIter>::value_type value_type;
	typedef typename std::vector<value_type>::iterator v_iter;
	typedef typename std::vector<randIter>::iterator indirect_iter;
	// sort indirect container
    std::vector<randIter> indirect_vec;
	{
		randIter ii = first;
		while (ii != last)
			indirect_vec.push_back(ii++);
	}
    std::sort(indirect_vec.begin(),  indirect_vec.end(), less_indirect<randIter, function>(f));

    // make new container
	std::vector<value_type> new_vec(last - first, value_type());

	// copy old values to new container in sorted order
	{
		assert(new_vec.size() == indirect_vec.size());
		indirect_iter sorted_iter = indirect_vec.begin();
		v_iter iter= new_vec.begin();
		v_iter end = new_vec.end();
		while (iter !=end)
		{
			swap(*iter, **sorted_iter);
			++iter;
			++sorted_iter;
		}
	}

	{
		v_iter iter= new_vec.begin();
		v_iter end = new_vec.end();
		while (iter !=end)
		{
			swap(*iter, *first);
			++iter;
			++first;
		}
	}
}

template<typename randIter>
void sort_with_swaps(randIter first, randIter last)
{
    typedef typename std::iterator_traits<randIter>::value_type value_type;
	sort_with_swaps<std::less<value_type>, randIter>(first, last, std::less<value_type>());
}



*/
template<typename function, typename randIter>
void sort_with_swaps(randIter first, randIter last, function f)
{
	std::vector<unsigned> indices(std::distance(first, last));

	sort_indices(first, last, indices, f);

	order_by_sorted_indices(first, last, indices);
}


// conflict with below

//template<typename randIter>
//void sort_with_swaps(randIter first, randIter last)
//{
//	std::vector<unsigned> indices(std::distance(first, last));
//
//	typedef typename std::iterator_traits<randIter>::value_type value_type;
//	sort_indices(first, last, indices, std::less<value_type>());
//	order_by_sorted_indices(first, last, indices);
//}



template<typename function, class CONT >
void sort_with_swaps(CONT& data, function f)
{
	std::vector<unsigned> indices(data.size());

	sort_indices(data.begin(), data.end(), indices, f);
	order_by_sorted_indices(data, indices);
}

template<typename T, template< typename T> class CONT >
void sort_with_swaps(CONT<T>& data)
{
	std::vector<unsigned> indices(data.size());
	sort_indices(data.begin(), data.end(), indices, std::less<T>());
	order_by_sorted_indices(data, indices);
}


template<typename _InputIter, typename _Function>
_Function
for_each_stride(_InputIter first, _InputIter last, unsigned stride, _Function f)
{
	if (first == last)
		return f;

	while (1)
	{
		f(*first);
		unsigned s = stride;
		while (s--)
		{
			++first;
			if (first == last)
				return f;
		}
	}
	return f;
}

/*****************************************************************************************
	for_each_pair


		  Apply a function to every element of a pair of ranges.
*****************************************************************************************/
template<typename _InputIter1, typename _InputIter2, typename _Function>
inline _Function
for_each_pair(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _Function f)
{
	for ( ; first1 != last1; ++first1, ++first2)
		f(*first1, *first2);
	return f;
}

/*****************************************************************************************
	for_each_iterpair_stride


		  Apply a function to iterators pointing to every nth elements of a pair of ranges
*****************************************************************************************/
template<typename _RandomAccessIter1, typename _RandomAccessIter2, typename _Function>
inline _Function
for_each_iterpair_stride(_RandomAccessIter1 first1, _RandomAccessIter1 last1,
					_RandomAccessIter2 first2, unsigned stride, _Function f)
{
	for ( ; first1 < last1; std::advance(first1, stride), std::advance(first2, stride))
		f(first1, first2);
	return f;
}




/*****************************************************************************************
	str_search_and_replace

		  Search for all instance of a string and replace with another
*****************************************************************************************/
inline void str_search_and_replace(std::string& str, const std::string& str_find, const std::string& replace)
{
	unsigned find_len = str_find.length();
	std::string::size_type pos = str.find(str_find);
	while (pos != std::string::npos)
	{
		str.replace(pos, find_len, replace);
		pos = str.find(str_find);
	}
}



/*****************************************************************************************
						find_pos_in_vector
******************************************************************************************/
template<typename T, typename CONT >
inline unsigned find_pos_in_vector(const CONT& vec, T t)
{
	return (std::find(vec.begin(), vec.end(), t) - vec.begin());
}

/*****************************************************************************************
						find_pos_in_vector
******************************************************************************************/
template<typename CONT, typename T >
inline unsigned find_if_pos_in_vector(const CONT& vec, T t)
{
	return (std::find_if(vec.begin(), vec.end(), t) - vec.begin());
}

/*****************************************************************************************
						find_pos_in_sorted
******************************************************************************************/
template<typename T, typename CONT >
inline unsigned find_pos_in_sorted(const CONT& vec, const T& t)
{
	typedef typename CONT::const_iterator citer;
	std::pair<citer, citer> found = std::equal_range(vec.begin(), vec.end(), t);
	if (found.first== found.second)
		return vec.size();
	else
		return found.first - vec.begin();
}

/*****************************************************************************************
						vector_release_mem
******************************************************************************************/
template<typename t> void vector_release_mem(std::vector<t>& vec)
{
	std::vector<t>().swap(vec);
}


/*****************************************************************************************
						deque_release_mem
******************************************************************************************/
template<typename t> void deque_release_mem(std::deque<t>& dec)
{
	std::deque<t>().swap(dec);
}


/*****************************************************************************************
						is_sorted

original source from sgi
include here only to ensure that it is always present

template <typename It, typename PRED>
bool is_sorted(It b, It e, PRED pred)
{
	return std::adjacent_find(b, e, std::not2(pred)) == e;}
******************************************************************************************/
namespace stlhelper
{
template<typename _ForwardIter, typename _StrictWeakOrdering>
    bool
    is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
    {

      if (__first == __last)
	return true;

      _ForwardIter __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next) {
	if (__comp(*__next, *__first))
	  return false;
      }

      return true;
    }

	template<typename _ForwardIter>
    bool
    is_sorted(_ForwardIter __first, _ForwardIter __last)
    {

      if (__first == __last)
		  return true;

      _ForwardIter __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next)
	  {
		  if (*__next < *__first)
			  return false;
      }

      return true;
    }

}


/*****************************************************************************************
						is_unique
******************************************************************************************/
namespace stlhelper
{
	template<typename _ForwardIter, typename _StrictWeakOrdering>
    bool is_unique(_ForwardIter first, _ForwardIter last, _StrictWeakOrdering comp)
    {
		return adjacent_find(first, last, comp) == last;
    }
	template<typename _ForwardIter>
    bool is_unique(_ForwardIter first, _ForwardIter last)
    {
		return adjacent_find(first, last) == last;
    }
}
/*****************************************************************************************
						transform_if
******************************************************************************************/
template <typename InputIterator, typename OutputIterator, typename UnaryOp>
inline OutputIterator transform_if(InputIterator first, InputIterator last,
									OutputIterator result, UnaryOp op)
{
    for (; first != last; ++first)
		if ((*result = op(*first)))
			++result;
    return result;
}


template <typename InputIterator, typename OutputIterator, typename UnaryOp, typename UnaryPred>
inline OutputIterator transform_if(InputIterator first, InputIterator last,
									OutputIterator result, UnaryOp op, UnaryPred pred)
{
    for (; first != last; ++first)
	{
		if (pred(*first))
		{
			*result = op(*first);
			++result;
		}
	}
    return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOp, class BinaryPred>
inline OutputIterator transform_if(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, OutputIterator result,
				BinaryOp binary_op, BinaryPred pred)
{
    for (; first1 != last1; ++first1, ++first2)
	{
		if (pred(*first1, *first2))
		{
			*result = binary_op(*first1, *first2);
			++result;
		}
	}
    return result;
}

/*****************************************************************************************
						compact_vector
******************************************************************************************/
template <typename T>
inline void compact_vector(std::vector<T>& c)
{
	std::vector<T>(c).swap(c);
}

/*****************************************************************************************
						count_removed_duplicates
******************************************************************************************/
template <typename Container>
unsigned count_removed_duplicates(Container& c)
{
	typename Container::iterator i = std::unique(c.begin(), c.end());
	unsigned cnt = std::distance(i, c.end());
	c.erase(i, c.end());
	return cnt;
}


template <class Container, class pred>
unsigned count_removed_duplicates(Container& c, pred p)
{
	typename Container::iterator i = std::unique(c.begin(),c.end(), p);
	unsigned cnt = std::distance(i, c.end());
	c.erase(i, c.end());
	return cnt;
}

/*****************************************************************************************
						remove_duplicates
******************************************************************************************/
template <class Container>
void remove_duplicates(Container& c)
{
	c.erase(std::unique(c.begin(),c.end()), c.end());
}


template <typename Container, typename pred>
void remove_duplicates(Container& c, pred p)
{
	c.erase(std::unique(c.begin(),c.end(), p), c.end());
}

/*****************************************************************************************
						remove_specified_duplicates
******************************************************************************************/
template<typename T>
struct op_eq_specified
{
	T specified;
	op_eq_specified(T specified_) : specified(specified_){}
	bool operator()(const T& a, const T& b)
	{ return a == b && a == specified; }
};


template <typename  Container, typename T>
Container& remove_specified_duplicates(Container& c, T t)
{
	typename Container::iterator first_unique =
		std::unique(c.begin(), c.end(), op_eq_specified<T>(t));
	if (first_unique != c.end())
		c.erase(first_unique, c.end());
	return c;
}



/*****************************************************************************************
						includes
******************************************************************************************/
template<class InputIterator, class Predicate>
bool includes_if(InputIterator first, InputIterator last,
                      Predicate pred)
{
	return std::find_if(first, last, pred) != last;
}


template< class Container, class Predicate>
inline bool includes_if(Container& c, Predicate pred)
{
	return includes(c.begin(), c.end(), pred);
}

template<class InputIterator, class T>
bool includes(InputIterator first, InputIterator last, T val)
{
	return std::find(first, last, val) != last;
}


template< class Container, class T>
inline bool includes(Container& c, T val)
{
	return includes(c.begin(),c.end(), val);
}

/*****************************************************************************************
						copy_if
******************************************************************************************/
template<class InIt, class OutIt, class PRED> inline
OutIt copy_if(InIt i, InIt last, OutIt dest, PRED pred)
{
	for (; i != last; ++i)
		if (pred(*i))
		{
			*dest++ = *i;
		}
	return (dest);
}

/*****************************************************************************************
						copy_if
******************************************************************************************/
template< typename Container1, typename Container2, typename PRED> inline
unsigned copy_if(const Container1& in, Container2& out, PRED pred)
{
	typedef typename  Container1::const_iterator citer;
	citer i = in.begin();
	citer end = in.end();
	unsigned cnt = 0;
	for (; i != end; ++i)
		if (pred(*i))
		{
			out.insert(out.end(), *i);
			++cnt;
		}
	return (cnt);
}

/*****************************************************************************************
						for_each_if
******************************************************************************************/
template<typename InIt, typename Fn, typename Pred> inline
Fn for_each_if(InIt i, InIt last, Fn op, Pred pred)
{
	for (; i != last; ++i)
		if (pred(*i))
			op(*i);
	return op;
}


/*****************************************************************************************
						erase_if_found
******************************************************************************************/
template< class Container, class iterator, class T>
inline void erase_if_found(Container& c, iterator start, iterator end, T t)
{
	iterator f = find(start, end, t);
	if (f != end)
		c.erase(f);
}


template< class Container, class T>
inline void erase_if_found(Container& c, T t)
{
	typename Container::iterator f = find(c.begin(),c.end(), t);
	if (f != c.end())
		c.erase(f);
}


/*****************************************************************************************
						min_max_element
******************************************************************************************/
template <class it> std::pair<it, it>
min_max_element (it first, it last)
{
    if (first == last)
		return(std::pair<it, it>(first, first));

    it minResult = first;
    it maxResult = first;

	// have two iterators which point to successive elements
    it second	  = first;
	++second;

	// compare two successive iterators to each other first and save one compare every
	// two elements
    while (second != last)
    {
		if (*first < *second)
		{
			if (*first < *minResult)
				minResult = first;
			if (*maxResult < *second)
				maxResult = second;
		}
		else if (*second < *first)
		{
			if (*maxResult < *first)
				maxResult = first;
			if (*second < *minResult)
				minResult = second;
		}
		++first;
		++second;
    }

	// handle odd number of elements
	if (first != last)
	{
		if (*first < *minResult)
			minResult = first;
		if (*maxResult < *first)
			maxResult = first;
	}
	return std::pair<it, it>(minResult, maxResult);
}

template <class it, class LessCompare> std::pair<it, it>
min_max_element (it first, it last, LessCompare comp)
{
    if (first == last)
		return std::pair<it, it> (first, first);

    it minResult = first;
    it maxResult = first;

	// have two iterators which point to successive elements
    it second	  = first;
	++second;

	// compare two successive iterators to each other first and save one compare every
	// two elements
    while (second != last)
    {
		if (comp(*first < *second))
		{
			if (comp(*first, *minResult))
				minResult = first;
			if (comp(*maxResult, *second))
				maxResult = second;
		}
		else if (comp(*second, *first))
		{
			if (comp(*maxResult, *first))
				maxResult = first;
			if (comp(*second, *minResult))
				minResult = second;
		}
		++first;
		++second;
    }

	// handle odd number of elements
	if (first != last)
	{
		if (comp(*first, *minResult))
			minResult = first;
		if (comp(*maxResult, *first))
			maxResult = first;
	}

	return std::pair<it, it>(minResult, maxResult);
}

/*****************************************************************************************
						set_mark_union
******************************************************************************************/
template<class _InIt1, class _InIt2, class PRED_Less, class OP_MARK>
inline
void set_mark_union(_InIt1 i1, _InIt1 last1,
					 _InIt2 i2, _InIt2 last2,
					 PRED_Less pred_less,
					 OP_MARK op_mark)
{
	if (i1 == last1 || i2 == last2)
		return;

	for (;;)
	{
		if (pred_less(*i1, *i2))
		{
			if (++i1 == last1)
				break;
		}
		else if (pred_less(*i2, *i1))
		{
			if (++i2 == last2)
				break;
		}
		else
		{
			op_mark(*i1, *i2);
			if (++i1 == last1 || ++i2 == last2)
				break;
		}
	}
}


/*****************************************************************************************
						mark_consecutive_duplicates
******************************************************************************************/
// assumes range sorted
template<typename It, typename OP_MARK>
inline
unsigned mark_consecutive_duplicates(It beg, It end, OP_MARK mark)
{
	// ignore empty range
	if (beg == end)
		return 0;

	// two iterators point to successive items
	It i1, i2;
	i1 = i2 = beg;
	i2++;

	unsigned cnt = 0;
	// remember last marked item to handle duplicates at the end of the range
	It last_marked = end;
	while (i2 != end)
	{
		// mark successive duplicates
		if (*i1 == *i2)
		{
			// mark start of new range of duplicates
			if (last_marked != i1)
			{
				cnt++;
				mark(*i1);
			}

			// mark and remember duplicate
			mark(*i2);
			last_marked = i2;
			cnt++;
		}
		++i1;
		++i2;
	}
	return cnt;
}


// assumes range sorted
template<typename It, typename OP_MARK, typename PRED_EQ>
inline
unsigned mark_consecutive_duplicates(It beg, It end, PRED_EQ pred_eq, OP_MARK mark)
{
	// ignore empty range
	if (beg == end)
		return 0;

	// two iterators point to successive items
	It i1 = beg;
	It i2 = beg;	++i2;

	unsigned cnt = 0;

	// remember last marked item to handle duplicates at the end of the range
	It last_marked = end;
	while (i2 != end)
	{
		// mark successive duplicates
		if (pred_eq(*i1 == *i2))
		{
			// mark start of new range of duplicates
			if (last_marked != i1)
			{
				mark(*i1);
				cnt++;
			}

			// mark and remember duplicate
			mark(*i2);
			last_marked = i2;
			cnt++;
		}
		++i1;
		++i2;
	}
	return cnt;
}

/*****************************************************************************************
						op_ignore

					do nothing function
******************************************************************************************/
template<typename T> struct op_ignore
{
	void operator ()(const T&)
	{
	}
};

#endif	//STLHELPER_H
